In [1]:
# temporairement je remprends la fonction de Sage
def binom(n, k):
return binomial(n,k) #
In [2]:
[[binom(n, k) for k in range(n+1)] for n in range(10)]
Out[2]:
[[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
[1, 5, 10, 10, 5, 1],
[1, 6, 15, 20, 15, 6, 1],
[1, 7, 21, 35, 35, 21, 7, 1],
[1, 8, 28, 56, 70, 56, 28, 8, 1],
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]
In [3]:
def list_BSnk(n, k):
if k > n:
return []
if k == 0:
return [n*[0]]
return ([[0]+x for x in list_BSnk(n-1, k)] +
[[1]+x for x in list_BSnk(n-1, k-1)])
In [4]:
list_BSnk(5,2)
Out[4]:
[[0, 0, 0, 1, 1],
[0, 0, 1, 0, 1],
[0, 0, 1, 1, 0],
[0, 1, 0, 0, 1],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 0],
[1, 0, 0, 0, 1],
[1, 0, 0, 1, 0],
[1, 0, 1, 0, 0],
[1, 1, 0, 0, 0]]
In [5]:
def rank_BSnk(x):
if not x: return 0
if x[0] == 0: # liste vide
return rank_BSnk(x[1:])
else:
return binom(len(x)-1, sum(x)-1) + rank_BSnk(x[1:])
def unrank_BSnk(n, k, i):
if n == 0:
return []
bn1k = binom(n-1, k)
if i < bn1k:
return [0]+unrank_BSnk(n-1, k, i)
else:
return [1]+unrank_BSnk(n-1, k-1, i-bn1k)
In [6]:
rank_BSnk([0,1,0,1,0])
Out[6]:
4
In [7]:
list_BSnk(5,2)[4]
Out[7]:
[0, 1, 0, 1, 0]
In [8]:
unrank_BSnk(5,2,4)
Out[8]:
[0, 1, 0, 1, 0]
In [ ]:
In [9]:
def binom(n,k):
if k > n:
return 0
if k == 0:
return 1
return binom(n-1, k) + binom(n-1, k-1)
In [10]:
[[binom(n, k) for k in range(n+1)] for n in range(10)]
Out[10]:
[[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
[1, 5, 10, 10, 5, 1],
[1, 6, 15, 20, 15, 6, 1],
[1, 7, 21, 35, 35, 21, 7, 1],
[1, 8, 28, 56, 70, 56, 28, 8, 1],
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]
In [11]:
binom(100, 50) # tres long...
---------------------------------------------------------------------------
KeyboardInterrupt Traceback (most recent call last)
<ipython-input-11-c06ccdfb8416> in <module>()
----> 1 binom(Integer(100), Integer(50)) # tres long...
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
<ipython-input-9-b355864de08d> in binom(n, k)
4 if k == Integer(0):
5 return Integer(1)
----> 6 return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))
src/cysignals/signals.pyx in cysignals.signals.python_check_interrupt (build/src/cysignals/signals.c:2854)()
src/cysignals/signals.pyx in cysignals.signals.sig_raise_exception (build/src/cysignals/signals.c:1303)()
KeyboardInterrupt:
Memoization en utilisant les decorateurs de Python/Sage:
In [12]:
@cached_function
def binom(n, k):
if k > n:
return 0
if k == 0:
return 1
return binom(n-1, k) + binom(n-1, k-1)
In [13]:
binom(100, 50)
Out[13]:
100891344545564193334812497256
Memoization a la main:
In [14]:
binomcache = {(0,0) : 1}
In [15]:
def binom(n, k):
if k > n: return 0
try:
return binomcache[n,k]
except KeyError:
if k == 0:
res = 1
else:
res = binom(n-1, k) + binom(n-1, k-1)
binomcache[n,k] = res
return res
In [16]:
binom(100, 50)
Out[16]:
100891344545564193334812497256
In [17]:
binomcache
Out[17]:
{(0, 0): 1,
(1, 0): 1,
(1, 1): 1,
(2, 0): 1,
(2, 1): 2,
(2, 2): 1,
(3, 0): 1,
(3, 1): 3,
(3, 2): 3,
(3, 3): 1,
(4, 0): 1,
(4, 1): 4,
(4, 2): 6,
(4, 3): 4,
(4, 4): 1,
(5, 0): 1,
(5, 1): 5,
(5, 2): 10,
(5, 3): 10,
(5, 4): 5,
(5, 5): 1,
(6, 0): 1,
(6, 1): 6,
(6, 2): 15,
(6, 3): 20,
(6, 4): 15,
(6, 5): 6,
(6, 6): 1,
(7, 0): 1,
(7, 1): 7,
(7, 2): 21,
(7, 3): 35,
(7, 4): 35,
(7, 5): 21,
(7, 6): 7,
(7, 7): 1,
(8, 0): 1,
(8, 1): 8,
(8, 2): 28,
(8, 3): 56,
(8, 4): 70,
(8, 5): 56,
(8, 6): 28,
(8, 7): 8,
(8, 8): 1,
(9, 0): 1,
(9, 1): 9,
(9, 2): 36,
(9, 3): 84,
(9, 4): 126,
(9, 5): 126,
(9, 6): 84,
(9, 7): 36,
(9, 8): 9,
(9, 9): 1,
(10, 0): 1,
(10, 1): 10,
(10, 2): 45,
(10, 3): 120,
(10, 4): 210,
(10, 5): 252,
(10, 6): 210,
(10, 7): 120,
(10, 8): 45,
(10, 9): 10,
(10, 10): 1,
(11, 0): 1,
(11, 1): 11,
(11, 2): 55,
(11, 3): 165,
(11, 4): 330,
(11, 5): 462,
(11, 6): 462,
(11, 7): 330,
(11, 8): 165,
(11, 9): 55,
(11, 10): 11,
(11, 11): 1,
(12, 0): 1,
(12, 1): 12,
(12, 2): 66,
(12, 3): 220,
(12, 4): 495,
(12, 5): 792,
(12, 6): 924,
(12, 7): 792,
(12, 8): 495,
(12, 9): 220,
(12, 10): 66,
(12, 11): 12,
(12, 12): 1,
(13, 0): 1,
(13, 1): 13,
(13, 2): 78,
(13, 3): 286,
(13, 4): 715,
(13, 5): 1287,
(13, 6): 1716,
(13, 7): 1716,
(13, 8): 1287,
(13, 9): 715,
(13, 10): 286,
(13, 11): 78,
(13, 12): 13,
(13, 13): 1,
(14, 0): 1,
(14, 1): 14,
(14, 2): 91,
(14, 3): 364,
(14, 4): 1001,
(14, 5): 2002,
(14, 6): 3003,
(14, 7): 3432,
(14, 8): 3003,
(14, 9): 2002,
(14, 10): 1001,
(14, 11): 364,
(14, 12): 91,
(14, 13): 14,
(14, 14): 1,
(15, 0): 1,
(15, 1): 15,
(15, 2): 105,
(15, 3): 455,
(15, 4): 1365,
(15, 5): 3003,
(15, 6): 5005,
(15, 7): 6435,
(15, 8): 6435,
(15, 9): 5005,
(15, 10): 3003,
(15, 11): 1365,
(15, 12): 455,
(15, 13): 105,
(15, 14): 15,
(15, 15): 1,
(16, 0): 1,
(16, 1): 16,
(16, 2): 120,
(16, 3): 560,
(16, 4): 1820,
(16, 5): 4368,
(16, 6): 8008,
(16, 7): 11440,
(16, 8): 12870,
(16, 9): 11440,
(16, 10): 8008,
(16, 11): 4368,
(16, 12): 1820,
(16, 13): 560,
(16, 14): 120,
(16, 15): 16,
(16, 16): 1,
(17, 0): 1,
(17, 1): 17,
(17, 2): 136,
(17, 3): 680,
(17, 4): 2380,
(17, 5): 6188,
(17, 6): 12376,
(17, 7): 19448,
(17, 8): 24310,
(17, 9): 24310,
(17, 10): 19448,
(17, 11): 12376,
(17, 12): 6188,
(17, 13): 2380,
(17, 14): 680,
(17, 15): 136,
(17, 16): 17,
(17, 17): 1,
(18, 0): 1,
(18, 1): 18,
(18, 2): 153,
(18, 3): 816,
(18, 4): 3060,
(18, 5): 8568,
(18, 6): 18564,
(18, 7): 31824,
(18, 8): 43758,
(18, 9): 48620,
(18, 10): 43758,
(18, 11): 31824,
(18, 12): 18564,
(18, 13): 8568,
(18, 14): 3060,
(18, 15): 816,
(18, 16): 153,
(18, 17): 18,
(18, 18): 1,
(19, 0): 1,
(19, 1): 19,
(19, 2): 171,
(19, 3): 969,
(19, 4): 3876,
(19, 5): 11628,
(19, 6): 27132,
(19, 7): 50388,
(19, 8): 75582,
(19, 9): 92378,
(19, 10): 92378,
(19, 11): 75582,
(19, 12): 50388,
(19, 13): 27132,
(19, 14): 11628,
(19, 15): 3876,
(19, 16): 969,
(19, 17): 171,
(19, 18): 19,
(19, 19): 1,
(20, 0): 1,
(20, 1): 20,
(20, 2): 190,
(20, 3): 1140,
(20, 4): 4845,
(20, 5): 15504,
(20, 6): 38760,
(20, 7): 77520,
(20, 8): 125970,
(20, 9): 167960,
(20, 10): 184756,
(20, 11): 167960,
(20, 12): 125970,
(20, 13): 77520,
(20, 14): 38760,
(20, 15): 15504,
(20, 16): 4845,
(20, 17): 1140,
(20, 18): 190,
(20, 19): 20,
(20, 20): 1,
(21, 0): 1,
(21, 1): 21,
(21, 2): 210,
(21, 3): 1330,
(21, 4): 5985,
(21, 5): 20349,
(21, 6): 54264,
(21, 7): 116280,
(21, 8): 203490,
(21, 9): 293930,
(21, 10): 352716,
(21, 11): 352716,
(21, 12): 293930,
(21, 13): 203490,
(21, 14): 116280,
(21, 15): 54264,
(21, 16): 20349,
(21, 17): 5985,
(21, 18): 1330,
(21, 19): 210,
(21, 20): 21,
(21, 21): 1,
(22, 0): 1,
(22, 1): 22,
(22, 2): 231,
(22, 3): 1540,
(22, 4): 7315,
(22, 5): 26334,
(22, 6): 74613,
(22, 7): 170544,
(22, 8): 319770,
(22, 9): 497420,
(22, 10): 646646,
(22, 11): 705432,
(22, 12): 646646,
(22, 13): 497420,
(22, 14): 319770,
(22, 15): 170544,
(22, 16): 74613,
(22, 17): 26334,
(22, 18): 7315,
(22, 19): 1540,
(22, 20): 231,
(22, 21): 22,
(22, 22): 1,
(23, 0): 1,
(23, 1): 23,
(23, 2): 253,
(23, 3): 1771,
(23, 4): 8855,
(23, 5): 33649,
(23, 6): 100947,
(23, 7): 245157,
(23, 8): 490314,
(23, 9): 817190,
(23, 10): 1144066,
(23, 11): 1352078,
(23, 12): 1352078,
(23, 13): 1144066,
(23, 14): 817190,
(23, 15): 490314,
(23, 16): 245157,
(23, 17): 100947,
(23, 18): 33649,
(23, 19): 8855,
(23, 20): 1771,
(23, 21): 253,
(23, 22): 23,
(23, 23): 1,
(24, 0): 1,
(24, 1): 24,
(24, 2): 276,
(24, 3): 2024,
(24, 4): 10626,
(24, 5): 42504,
(24, 6): 134596,
(24, 7): 346104,
(24, 8): 735471,
(24, 9): 1307504,
(24, 10): 1961256,
(24, 11): 2496144,
(24, 12): 2704156,
(24, 13): 2496144,
(24, 14): 1961256,
(24, 15): 1307504,
(24, 16): 735471,
(24, 17): 346104,
(24, 18): 134596,
(24, 19): 42504,
(24, 20): 10626,
(24, 21): 2024,
(24, 22): 276,
(24, 23): 24,
(24, 24): 1,
(25, 0): 1,
(25, 1): 25,
(25, 2): 300,
(25, 3): 2300,
(25, 4): 12650,
(25, 5): 53130,
(25, 6): 177100,
(25, 7): 480700,
(25, 8): 1081575,
(25, 9): 2042975,
(25, 10): 3268760,
(25, 11): 4457400,
(25, 12): 5200300,
(25, 13): 5200300,
(25, 14): 4457400,
(25, 15): 3268760,
(25, 16): 2042975,
(25, 17): 1081575,
(25, 18): 480700,
(25, 19): 177100,
(25, 20): 53130,
(25, 21): 12650,
(25, 22): 2300,
(25, 23): 300,
(25, 24): 25,
(25, 25): 1,
(26, 0): 1,
(26, 1): 26,
(26, 2): 325,
(26, 3): 2600,
(26, 4): 14950,
(26, 5): 65780,
(26, 6): 230230,
(26, 7): 657800,
(26, 8): 1562275,
(26, 9): 3124550,
(26, 10): 5311735,
(26, 11): 7726160,
(26, 12): 9657700,
(26, 13): 10400600,
(26, 14): 9657700,
(26, 15): 7726160,
(26, 16): 5311735,
(26, 17): 3124550,
(26, 18): 1562275,
(26, 19): 657800,
(26, 20): 230230,
(26, 21): 65780,
(26, 22): 14950,
(26, 23): 2600,
(26, 24): 325,
(26, 25): 26,
(26, 26): 1,
(27, 0): 1,
(27, 1): 27,
(27, 2): 351,
(27, 3): 2925,
(27, 4): 17550,
(27, 5): 80730,
(27, 6): 296010,
(27, 7): 888030,
(27, 8): 2220075,
(27, 9): 4686825,
(27, 10): 8436285,
(27, 11): 13037895,
(27, 12): 17383860,
(27, 13): 20058300,
(27, 14): 20058300,
(27, 15): 17383860,
(27, 16): 13037895,
(27, 17): 8436285,
(27, 18): 4686825,
(27, 19): 2220075,
(27, 20): 888030,
(27, 21): 296010,
(27, 22): 80730,
(27, 23): 17550,
(27, 24): 2925,
(27, 25): 351,
(27, 26): 27,
(27, 27): 1,
(28, 0): 1,
(28, 1): 28,
(28, 2): 378,
(28, 3): 3276,
(28, 4): 20475,
(28, 5): 98280,
(28, 6): 376740,
(28, 7): 1184040,
(28, 8): 3108105,
(28, 9): 6906900,
(28, 10): 13123110,
(28, 11): 21474180,
(28, 12): 30421755,
(28, 13): 37442160,
(28, 14): 40116600,
(28, 15): 37442160,
(28, 16): 30421755,
(28, 17): 21474180,
(28, 18): 13123110,
(28, 19): 6906900,
(28, 20): 3108105,
(28, 21): 1184040,
(28, 22): 376740,
(28, 23): 98280,
(28, 24): 20475,
(28, 25): 3276,
(28, 26): 378,
(28, 27): 28,
(28, 28): 1,
(29, 0): 1,
(29, 1): 29,
(29, 2): 406,
(29, 3): 3654,
(29, 4): 23751,
(29, 5): 118755,
(29, 6): 475020,
(29, 7): 1560780,
(29, 8): 4292145,
(29, 9): 10015005,
(29, 10): 20030010,
(29, 11): 34597290,
(29, 12): 51895935,
(29, 13): 67863915,
(29, 14): 77558760,
(29, 15): 77558760,
(29, 16): 67863915,
(29, 17): 51895935,
(29, 18): 34597290,
(29, 19): 20030010,
(29, 20): 10015005,
(29, 21): 4292145,
(29, 22): 1560780,
(29, 23): 475020,
(29, 24): 118755,
(29, 25): 23751,
(29, 26): 3654,
(29, 27): 406,
(29, 28): 29,
(29, 29): 1,
(30, 0): 1,
(30, 1): 30,
(30, 2): 435,
(30, 3): 4060,
(30, 4): 27405,
(30, 5): 142506,
(30, 6): 593775,
(30, 7): 2035800,
(30, 8): 5852925,
(30, 9): 14307150,
(30, 10): 30045015,
(30, 11): 54627300,
(30, 12): 86493225,
(30, 13): 119759850,
(30, 14): 145422675,
(30, 15): 155117520,
(30, 16): 145422675,
(30, 17): 119759850,
(30, 18): 86493225,
(30, 19): 54627300,
(30, 20): 30045015,
(30, 21): 14307150,
(30, 22): 5852925,
(30, 23): 2035800,
(30, 24): 593775,
(30, 25): 142506,
(30, 26): 27405,
(30, 27): 4060,
(30, 28): 435,
(30, 29): 30,
(30, 30): 1,
(31, 0): 1,
(31, 1): 31,
(31, 2): 465,
(31, 3): 4495,
(31, 4): 31465,
(31, 5): 169911,
(31, 6): 736281,
(31, 7): 2629575,
(31, 8): 7888725,
(31, 9): 20160075,
(31, 10): 44352165,
(31, 11): 84672315,
(31, 12): 141120525,
(31, 13): 206253075,
(31, 14): 265182525,
(31, 15): 300540195,
(31, 16): 300540195,
(31, 17): 265182525,
(31, 18): 206253075,
(31, 19): 141120525,
(31, 20): 84672315,
(31, 21): 44352165,
(31, 22): 20160075,
(31, 23): 7888725,
(31, 24): 2629575,
(31, 25): 736281,
(31, 26): 169911,
(31, 27): 31465,
(31, 28): 4495,
(31, 29): 465,
(31, 30): 31,
(31, 31): 1,
(32, 0): 1,
(32, 1): 32,
(32, 2): 496,
(32, 3): 4960,
(32, 4): 35960,
(32, 5): 201376,
(32, 6): 906192,
(32, 7): 3365856,
(32, 8): 10518300,
(32, 9): 28048800,
(32, 10): 64512240,
(32, 11): 129024480,
(32, 12): 225792840,
(32, 13): 347373600,
(32, 14): 471435600,
(32, 15): 565722720,
(32, 16): 601080390,
(32, 17): 565722720,
(32, 18): 471435600,
(32, 19): 347373600,
(32, 20): 225792840,
(32, 21): 129024480,
(32, 22): 64512240,
(32, 23): 28048800,
(32, 24): 10518300,
(32, 25): 3365856,
(32, 26): 906192,
(32, 27): 201376,
(32, 28): 35960,
(32, 29): 4960,
(32, 30): 496,
(32, 31): 32,
(32, 32): 1,
(33, 0): 1,
(33, 1): 33,
(33, 2): 528,
(33, 3): 5456,
(33, 4): 40920,
(33, 5): 237336,
(33, 6): 1107568,
(33, 7): 4272048,
(33, 8): 13884156,
(33, 9): 38567100,
(33, 10): 92561040,
(33, 11): 193536720,
(33, 12): 354817320,
(33, 13): 573166440,
(33, 14): 818809200,
(33, 15): 1037158320,
(33, 16): 1166803110,
(33, 17): 1166803110,
(33, 18): 1037158320,
(33, 19): 818809200,
(33, 20): 573166440,
(33, 21): 354817320,
(33, 22): 193536720,
(33, 23): 92561040,
(33, 24): 38567100,
(33, 25): 13884156,
(33, 26): 4272048,
(33, 27): 1107568,
(33, 28): 237336,
(33, 29): 40920,
(33, 30): 5456,
(33, 31): 528,
(33, 32): 33,
(33, 33): 1,
(34, 0): 1,
(34, 1): 34,
(34, 2): 561,
(34, 3): 5984,
(34, 4): 46376,
(34, 5): 278256,
(34, 6): 1344904,
(34, 7): 5379616,
(34, 8): 18156204,
(34, 9): 52451256,
(34, 10): 131128140,
(34, 11): 286097760,
(34, 12): 548354040,
(34, 13): 927983760,
(34, 14): 1391975640,
(34, 15): 1855967520,
(34, 16): 2203961430,
(34, 17): 2333606220,
(34, 18): 2203961430,
(34, 19): 1855967520,
(34, 20): 1391975640,
(34, 21): 927983760,
(34, 22): 548354040,
(34, 23): 286097760,
(34, 24): 131128140,
(34, 25): 52451256,
(34, 26): 18156204,
(34, 27): 5379616,
(34, 28): 1344904,
(34, 29): 278256,
(34, 30): 46376,
(34, 31): 5984,
(34, 32): 561,
(34, 33): 34,
(34, 34): 1,
(35, 0): 1,
(35, 1): 35,
(35, 2): 595,
(35, 3): 6545,
(35, 4): 52360,
(35, 5): 324632,
(35, 6): 1623160,
(35, 7): 6724520,
(35, 8): 23535820,
(35, 9): 70607460,
(35, 10): 183579396,
(35, 11): 417225900,
(35, 12): 834451800,
(35, 13): 1476337800,
(35, 14): 2319959400,
(35, 15): 3247943160,
(35, 16): 4059928950,
(35, 17): 4537567650,
(35, 18): 4537567650,
(35, 19): 4059928950,
(35, 20): 3247943160,
(35, 21): 2319959400,
(35, 22): 1476337800,
(35, 23): 834451800,
(35, 24): 417225900,
(35, 25): 183579396,
(35, 26): 70607460,
(35, 27): 23535820,
(35, 28): 6724520,
(35, 29): 1623160,
(35, 30): 324632,
(35, 31): 52360,
(35, 32): 6545,
(35, 33): 595,
(35, 34): 35,
(35, 35): 1,
(36, 0): 1,
(36, 1): 36,
(36, 2): 630,
(36, 3): 7140,
(36, 4): 58905,
(36, 5): 376992,
(36, 6): 1947792,
(36, 7): 8347680,
(36, 8): 30260340,
(36, 9): 94143280,
(36, 10): 254186856,
(36, 11): 600805296,
(36, 12): 1251677700,
(36, 13): 2310789600,
(36, 14): 3796297200,
(36, 15): 5567902560,
(36, 16): 7307872110,
(36, 17): 8597496600,
(36, 18): 9075135300,
(36, 19): 8597496600,
(36, 20): 7307872110,
(36, 21): 5567902560,
(36, 22): 3796297200,
(36, 23): 2310789600,
(36, 24): 1251677700,
(36, 25): 600805296,
(36, 26): 254186856,
(36, 27): 94143280,
(36, 28): 30260340,
(36, 29): 8347680,
(36, 30): 1947792,
(36, 31): 376992,
(36, 32): 58905,
(36, 33): 7140,
(36, 34): 630,
(36, 35): 36,
(36, 36): 1,
(37, 0): 1,
(37, 1): 37,
(37, 2): 666,
(37, 3): 7770,
(37, 4): 66045,
(37, 5): 435897,
(37, 6): 2324784,
(37, 7): 10295472,
(37, 8): 38608020,
(37, 9): 124403620,
(37, 10): 348330136,
(37, 11): 854992152,
(37, 12): 1852482996,
(37, 13): 3562467300,
(37, 14): 6107086800,
(37, 15): 9364199760,
(37, 16): 12875774670,
(37, 17): 15905368710,
(37, 18): 17672631900,
(37, 19): 17672631900,
(37, 20): 15905368710,
(37, 21): 12875774670,
(37, 22): 9364199760,
(37, 23): 6107086800,
(37, 24): 3562467300,
(37, 25): 1852482996,
(37, 26): 854992152,
(37, 27): 348330136,
(37, 28): 124403620,
(37, 29): 38608020,
(37, 30): 10295472,
(37, 31): 2324784,
(37, 32): 435897,
(37, 33): 66045,
(37, 34): 7770,
(37, 35): 666,
(37, 36): 37,
(37, 37): 1,
(38, 0): 1,
(38, 1): 38,
(38, 2): 703,
(38, 3): 8436,
(38, 4): 73815,
(38, 5): 501942,
(38, 6): 2760681,
(38, 7): 12620256,
(38, 8): 48903492,
(38, 9): 163011640,
(38, 10): 472733756,
(38, 11): 1203322288,
(38, 12): 2707475148,
(38, 13): 5414950296,
(38, 14): 9669554100,
(38, 15): 15471286560,
(38, 16): 22239974430,
(38, 17): 28781143380,
(38, 18): 33578000610,
(38, 19): 35345263800,
(38, 20): 33578000610,
(38, 21): 28781143380,
(38, 22): 22239974430,
(38, 23): 15471286560,
(38, 24): 9669554100,
(38, 25): 5414950296,
(38, 26): 2707475148,
(38, 27): 1203322288,
(38, 28): 472733756,
(38, 29): 163011640,
(38, 30): 48903492,
(38, 31): 12620256,
(38, 32): 2760681,
(38, 33): 501942,
(38, 34): 73815,
(38, 35): 8436,
(38, 36): 703,
(38, 37): 38,
(38, 38): 1,
(39, 0): 1,
(39, 1): 39,
(39, 2): 741,
(39, 3): 9139,
(39, 4): 82251,
(39, 5): 575757,
(39, 6): 3262623,
(39, 7): 15380937,
(39, 8): 61523748,
(39, 9): 211915132,
(39, 10): 635745396,
(39, 11): 1676056044,
(39, 12): 3910797436,
(39, 13): 8122425444,
(39, 14): 15084504396,
(39, 15): 25140840660,
(39, 16): 37711260990,
(39, 17): 51021117810,
(39, 18): 62359143990,
(39, 19): 68923264410,
(39, 20): 68923264410,
(39, 21): 62359143990,
(39, 22): 51021117810,
(39, 23): 37711260990,
(39, 24): 25140840660,
(39, 25): 15084504396,
(39, 26): 8122425444,
(39, 27): 3910797436,
(39, 28): 1676056044,
(39, 29): 635745396,
(39, 30): 211915132,
(39, 31): 61523748,
(39, 32): 15380937,
(39, 33): 3262623,
(39, 34): 575757,
(39, 35): 82251,
(39, 36): 9139,
(39, 37): 741,
(39, 38): 39,
(39, 39): 1,
(40, 0): 1,
(40, 1): 40,
(40, 2): 780,
(40, 3): 9880,
(40, 4): 91390,
(40, 5): 658008,
(40, 6): 3838380,
(40, 7): 18643560,
(40, 8): 76904685,
(40, 9): 273438880,
(40, 10): 847660528,
(40, 11): 2311801440,
(40, 12): 5586853480,
(40, 13): 12033222880,
(40, 14): 23206929840,
(40, 15): 40225345056,
(40, 16): 62852101650,
(40, 17): 88732378800,
(40, 18): 113380261800,
(40, 19): 131282408400,
(40, 20): 137846528820,
(40, 21): 131282408400,
(40, 22): 113380261800,
(40, 23): 88732378800,
(40, 24): 62852101650,
(40, 25): 40225345056,
(40, 26): 23206929840,
(40, 27): 12033222880,
(40, 28): 5586853480,
(40, 29): 2311801440,
(40, 30): 847660528,
(40, 31): 273438880,
(40, 32): 76904685,
(40, 33): 18643560,
(40, 34): 3838380,
(40, 35): 658008,
(40, 36): 91390,
(40, 37): 9880,
(40, 38): 780,
(40, 39): 40,
(40, 40): 1,
(41, 0): 1,
(41, 1): 41,
(41, 2): 820,
(41, 3): 10660,
(41, 4): 101270,
(41, 5): 749398,
(41, 6): 4496388,
(41, 7): 22481940,
(41, 8): 95548245,
(41, 9): 350343565,
(41, 10): 1121099408,
(41, 11): 3159461968,
(41, 12): 7898654920,
(41, 13): 17620076360,
(41, 14): 35240152720,
(41, 15): 63432274896,
(41, 16): 103077446706,
(41, 17): 151584480450,
(41, 18): 202112640600,
(41, 19): 244662670200,
(41, 20): 269128937220,
(41, 21): 269128937220,
(41, 22): 244662670200,
(41, 23): 202112640600,
(41, 24): 151584480450,
(41, 25): 103077446706,
(41, 26): 63432274896,
(41, 27): 35240152720,
(41, 28): 17620076360,
(41, 29): 7898654920,
(41, 30): 3159461968,
(41, 31): 1121099408,
(41, 32): 350343565,
(41, 33): 95548245,
(41, 34): 22481940,
(41, 35): 4496388,
(41, 36): 749398,
(41, 37): 101270,
(41, 38): 10660,
(41, 39): 820,
(41, 40): 41,
(41, 41): 1,
(42, 0): 1,
(42, 1): 42,
(42, 2): 861,
(42, 3): 11480,
(42, 4): 111930,
(42, 5): 850668,
(42, 6): 5245786,
(42, 7): 26978328,
(42, 8): 118030185,
(42, 9): 445891810,
(42, 10): 1471442973,
(42, 11): 4280561376,
(42, 12): 11058116888,
(42, 13): 25518731280,
(42, 14): 52860229080,
(42, 15): 98672427616,
(42, 16): 166509721602,
(42, 17): 254661927156,
(42, 18): 353697121050,
(42, 19): 446775310800,
(42, 20): 513791607420,
(42, 21): 538257874440,
(42, 22): 513791607420,
(42, 23): 446775310800,
(42, 24): 353697121050,
(42, 25): 254661927156,
(42, 26): 166509721602,
(42, 27): 98672427616,
(42, 28): 52860229080,
(42, 29): 25518731280,
(42, 30): 11058116888,
(42, 31): 4280561376,
(42, 32): 1471442973,
(42, 33): 445891810,
(42, 34): 118030185,
(42, 35): 26978328,
(42, 36): 5245786,
(42, 37): 850668,
(42, 38): 111930,
(42, 39): 11480,
(42, 40): 861,
(42, 41): 42,
(42, 42): 1,
(43, 0): 1,
(43, 1): 43,
(43, 2): 903,
(43, 3): 12341,
(43, 4): 123410,
(43, 5): 962598,
(43, 6): 6096454,
(43, 7): 32224114,
(43, 8): 145008513,
(43, 9): 563921995,
(43, 10): 1917334783,
(43, 11): 5752004349,
(43, 12): 15338678264,
(43, 13): 36576848168,
(43, 14): 78378960360,
(43, 15): 151532656696,
(43, 16): 265182149218,
(43, 17): 421171648758,
(43, 18): 608359048206,
(43, 19): 800472431850,
(43, 20): 960566918220,
(43, 21): 1052049481860,
(43, 22): 1052049481860,
(43, 23): 960566918220,
(43, 24): 800472431850,
(43, 25): 608359048206,
(43, 26): 421171648758,
(43, 27): 265182149218,
(43, 28): 151532656696,
(43, 29): 78378960360,
(43, 30): 36576848168,
(43, 31): 15338678264,
(43, 32): 5752004349,
(43, 33): 1917334783,
(43, 34): 563921995,
(43, 35): 145008513,
(43, 36): 32224114,
(43, 37): 6096454,
(43, 38): 962598,
(43, 39): 123410,
(43, 40): 12341,
(43, 41): 903,
(43, 42): 43,
(43, 43): 1,
(44, 0): 1,
(44, 1): 44,
(44, 2): 946,
(44, 3): 13244,
(44, 4): 135751,
(44, 5): 1086008,
(44, 6): 7059052,
(44, 7): 38320568,
(44, 8): 177232627,
(44, 9): 708930508,
(44, 10): 2481256778,
(44, 11): 7669339132,
(44, 12): 21090682613,
(44, 13): 51915526432,
(44, 14): 114955808528,
(44, 15): 229911617056,
(44, 16): 416714805914,
(44, 17): 686353797976,
(44, 18): 1029530696964,
(44, 19): 1408831480056,
(44, 20): 1761039350070,
(44, 21): 2012616400080,
(44, 22): 2104098963720,
(44, 23): 2012616400080,
(44, 24): 1761039350070,
(44, 25): 1408831480056,
(44, 26): 1029530696964,
(44, 27): 686353797976,
(44, 28): 416714805914,
(44, 29): 229911617056,
(44, 30): 114955808528,
(44, 31): 51915526432,
(44, 32): 21090682613,
(44, 33): 7669339132,
(44, 34): 2481256778,
(44, 35): 708930508,
(44, 36): 177232627,
(44, 37): 38320568,
(44, 38): 7059052,
(44, 39): 1086008,
(44, 40): 135751,
(44, 41): 13244,
(44, 42): 946,
(44, 43): 44,
(44, 44): 1,
(45, 0): 1,
(45, 1): 45,
(45, 2): 990,
(45, 3): 14190,
(45, 4): 148995,
(45, 5): 1221759,
(45, 6): 8145060,
(45, 7): 45379620,
(45, 8): 215553195,
(45, 9): 886163135,
(45, 10): 3190187286,
(45, 11): 10150595910,
(45, 12): 28760021745,
(45, 13): 73006209045,
(45, 14): 166871334960,
(45, 15): 344867425584,
(45, 16): 646626422970,
(45, 17): 1103068603890,
(45, 18): 1715884494940,
(45, 19): 2438362177020,
(45, 20): 3169870830126,
(45, 21): 3773655750150,
(45, 22): 4116715363800,
(45, 23): 4116715363800,
(45, 24): 3773655750150,
(45, 25): 3169870830126,
(45, 26): 2438362177020,
(45, 27): 1715884494940,
(45, 28): 1103068603890,
(45, 29): 646626422970,
(45, 30): 344867425584,
(45, 31): 166871334960,
(45, 32): 73006209045,
(45, 33): 28760021745,
(45, 34): 10150595910,
(45, 35): 3190187286,
(45, 36): 886163135,
(45, 37): 215553195,
(45, 38): 45379620,
(45, 39): 8145060,
(45, 40): 1221759,
(45, 41): 148995,
(45, 42): 14190,
(45, 43): 990,
(45, 44): 45,
(45, 45): 1,
(46, 0): 1,
(46, 1): 46,
(46, 2): 1035,
(46, 3): 15180,
(46, 4): 163185,
(46, 5): 1370754,
(46, 6): 9366819,
(46, 7): 53524680,
(46, 8): 260932815,
(46, 9): 1101716330,
(46, 10): 4076350421,
(46, 11): 13340783196,
(46, 12): 38910617655,
(46, 13): 101766230790,
(46, 14): 239877544005,
(46, 15): 511738760544,
(46, 16): 991493848554,
(46, 17): 1749695026860,
(46, 18): 2818953098830,
(46, 19): 4154246671960,
(46, 20): 5608233007146,
(46, 21): 6943526580276,
(46, 22): 7890371113950,
(46, 23): 8233430727600,
(46, 24): 7890371113950,
(46, 25): 6943526580276,
(46, 26): 5608233007146,
(46, 27): 4154246671960,
(46, 28): 2818953098830,
(46, 29): 1749695026860,
(46, 30): 991493848554,
(46, 31): 511738760544,
(46, 32): 239877544005,
(46, 33): 101766230790,
(46, 34): 38910617655,
(46, 35): 13340783196,
(46, 36): 4076350421,
(46, 37): 1101716330,
(46, 38): 260932815,
(46, 39): 53524680,
(46, 40): 9366819,
(46, 41): 1370754,
(46, 42): 163185,
(46, 43): 15180,
(46, 44): 1035,
(46, 45): 46,
(46, 46): 1,
(47, 0): 1,
(47, 1): 47,
(47, 2): 1081,
(47, 3): 16215,
(47, 4): 178365,
(47, 5): 1533939,
(47, 6): 10737573,
(47, 7): 62891499,
(47, 8): 314457495,
(47, 9): 1362649145,
(47, 10): 5178066751,
(47, 11): 17417133617,
(47, 12): 52251400851,
(47, 13): 140676848445,
(47, 14): 341643774795,
(47, 15): 751616304549,
(47, 16): 1503232609098,
(47, 17): 2741188875414,
(47, 18): 4568648125690,
(47, 19): 6973199770790,
(47, 20): 9762479679106,
(47, 21): 12551759587422,
(47, 22): 14833897694226,
(47, 23): 16123801841550,
(47, 24): 16123801841550,
(47, 25): 14833897694226,
(47, 26): 12551759587422,
(47, 27): 9762479679106,
(47, 28): 6973199770790,
(47, 29): 4568648125690,
(47, 30): 2741188875414,
(47, 31): 1503232609098,
(47, 32): 751616304549,
(47, 33): 341643774795,
(47, 34): 140676848445,
(47, 35): 52251400851,
(47, 36): 17417133617,
(47, 37): 5178066751,
(47, 38): 1362649145,
(47, 39): 314457495,
(47, 40): 62891499,
(47, 41): 10737573,
(47, 42): 1533939,
(47, 43): 178365,
(47, 44): 16215,
(47, 45): 1081,
(47, 46): 47,
(47, 47): 1,
(48, 0): 1,
(48, 1): 48,
(48, 2): 1128,
(48, 3): 17296,
(48, 4): 194580,
(48, 5): 1712304,
(48, 6): 12271512,
(48, 7): 73629072,
(48, 8): 377348994,
(48, 9): 1677106640,
(48, 10): 6540715896,
(48, 11): 22595200368,
(48, 12): 69668534468,
(48, 13): 192928249296,
(48, 14): 482320623240,
(48, 15): 1093260079344,
(48, 16): 2254848913647,
(48, 17): 4244421484512,
(48, 18): 7309837001104,
(48, 19): 11541847896480,
(48, 20): 16735679449896,
(48, 21): 22314239266528,
(48, 22): 27385657281648,
(48, 23): 30957699535776,
(48, 24): 32247603683100,
(48, 25): 30957699535776,
(48, 26): 27385657281648,
(48, 27): 22314239266528,
(48, 28): 16735679449896,
(48, 29): 11541847896480,
(48, 30): 7309837001104,
(48, 31): 4244421484512,
(48, 32): 2254848913647,
(48, 33): 1093260079344,
(48, 34): 482320623240,
(48, 35): 192928249296,
(48, 36): 69668534468,
(48, 37): 22595200368,
(48, 38): 6540715896,
(48, 39): 1677106640,
(48, 40): 377348994,
(48, 41): 73629072,
(48, 42): 12271512,
(48, 43): 1712304,
(48, 44): 194580,
(48, 45): 17296,
(48, 46): 1128,
(48, 47): 48,
(48, 48): 1,
(49, 0): 1,
(49, 1): 49,
(49, 2): 1176,
(49, 3): 18424,
(49, 4): 211876,
(49, 5): 1906884,
(49, 6): 13983816,
(49, 7): 85900584,
(49, 8): 450978066,
(49, 9): 2054455634,
(49, 10): 8217822536,
(49, 11): 29135916264,
(49, 12): 92263734836,
(49, 13): 262596783764,
(49, 14): 675248872536,
(49, 15): 1575580702584,
(49, 16): 3348108992991,
(49, 17): 6499270398159,
(49, 18): 11554258485616,
(49, 19): 18851684897584,
(49, 20): 28277527346376,
(49, 21): 39049918716424,
(49, 22): 49699896548176,
(49, 23): 58343356817424,
(49, 24): 63205303218876,
(49, 25): 63205303218876,
(49, 26): 58343356817424,
(49, 27): 49699896548176,
(49, 28): 39049918716424,
(49, 29): 28277527346376,
(49, 30): 18851684897584,
(49, 31): 11554258485616,
(49, 32): 6499270398159,
(49, 33): 3348108992991,
(49, 34): 1575580702584,
(49, 35): 675248872536,
(49, 36): 262596783764,
(49, 37): 92263734836,
(49, 38): 29135916264,
(49, 39): 8217822536,
(49, 40): 2054455634,
(49, 41): 450978066,
(49, 42): 85900584,
(49, 43): 13983816,
(49, 44): 1906884,
(49, 45): 211876,
(49, 46): 18424,
(49, 47): 1176,
(49, 48): 49,
(49, 49): 1,
(50, 0): 1,
(50, 1): 50,
(50, 2): 1225,
(50, 3): 19600,
(50, 4): 230300,
(50, 5): 2118760,
(50, 6): 15890700,
(50, 7): 99884400,
(50, 8): 536878650,
(50, 9): 2505433700,
(50, 10): 10272278170,
(50, 11): 37353738800,
(50, 12): 121399651100,
(50, 13): 354860518600,
(50, 14): 937845656300,
(50, 15): 2250829575120,
(50, 16): 4923689695575,
(50, 17): 9847379391150,
(50, 18): 18053528883775,
(50, 19): 30405943383200,
(50, 20): 47129212243960,
(50, 21): 67327446062800,
(50, 22): 88749815264600,
(50, 23): 108043253365600,
(50, 24): 121548660036300,
(50, 25): 126410606437752,
(50, 26): 121548660036300,
(50, 27): 108043253365600,
(50, 28): 88749815264600,
(50, 29): 67327446062800,
(50, 30): 47129212243960,
(50, 31): 30405943383200,
(50, 32): 18053528883775,
(50, 33): 9847379391150,
(50, 34): 4923689695575,
(50, 35): 2250829575120,
(50, 36): 937845656300,
(50, 37): 354860518600,
(50, 38): 121399651100,
(50, 39): 37353738800,
(50, 40): 10272278170,
(50, 41): 2505433700,
(50, 42): 536878650,
(50, 43): 99884400,
(50, 44): 15890700,
(50, 45): 2118760,
(50, 46): 230300,
(50, 47): 19600,
(50, 48): 1225,
(50, 49): 50,
(50, 50): 1,
(51, 1): 51,
(51, 2): 1275,
(51, 3): 20825,
(51, 4): 249900,
(51, 5): 2349060,
(51, 6): 18009460,
(51, 7): 115775100,
(51, 8): 636763050,
(51, 9): 3042312350,
(51, 10): 12777711870,
(51, 11): 47626016970,
(51, 12): 158753389900,
(51, 13): 476260169700,
(51, 14): 1292706174900,
(51, 15): 3188675231420,
(51, 16): 7174519270695,
(51, 17): 14771069086725,
(51, 18): 27900908274925,
(51, 19): 48459472266975,
(51, 20): 77535155627160,
(51, 21): 114456658306760,
(51, 22): 156077261327400,
(51, 23): 196793068630200,
(51, 24): 229591913401900,
(51, 25): 247959266474052,
(51, 26): 247959266474052,
(51, 27): 229591913401900,
(51, 28): 196793068630200,
(51, 29): 156077261327400,
(51, 30): 114456658306760,
(51, 31): 77535155627160,
(51, 32): 48459472266975,
(51, 33): 27900908274925,
(51, 34): 14771069086725,
(51, 35): 7174519270695,
(51, 36): 3188675231420,
(51, 37): 1292706174900,
(51, 38): 476260169700,
(51, 39): 158753389900,
(51, 40): 47626016970,
(51, 41): 12777711870,
(51, 42): 3042312350,
(51, 43): 636763050,
(51, 44): 115775100,
(51, 45): 18009460,
(51, 46): 2349060,
(51, 47): 249900,
(51, 48): 20825,
(51, 49): 1275,
(51, 50): 51,
(52, 2): 1326,
(52, 3): 22100,
(52, 4): 270725,
(52, 5): 2598960,
(52, 6): 20358520,
(52, 7): 133784560,
(52, 8): 752538150,
(52, 9): 3679075400,
(52, 10): 15820024220,
(52, 11): 60403728840,
(52, 12): 206379406870,
(52, 13): 635013559600,
(52, 14): 1768966344600,
(52, 15): 4481381406320,
(52, 16): 10363194502115,
(52, 17): 21945588357420,
(52, 18): 42671977361650,
(52, 19): 76360380541900,
(52, 20): 125994627894135,
(52, 21): 191991813933920,
(52, 22): 270533919634160,
(52, 23): 352870329957600,
(52, 24): 426384982032100,
(52, 25): 477551179875952,
(52, 26): 495918532948104,
(52, 27): 477551179875952,
(52, 28): 426384982032100,
(52, 29): 352870329957600,
(52, 30): 270533919634160,
(52, 31): 191991813933920,
(52, 32): 125994627894135,
(52, 33): 76360380541900,
(52, 34): 42671977361650,
(52, 35): 21945588357420,
(52, 36): 10363194502115,
(52, 37): 4481381406320,
(52, 38): 1768966344600,
(52, 39): 635013559600,
(52, 40): 206379406870,
(52, 41): 60403728840,
(52, 42): 15820024220,
(52, 43): 3679075400,
(52, 44): 752538150,
(52, 45): 133784560,
(52, 46): 20358520,
(52, 47): 2598960,
(52, 48): 270725,
(52, 49): 22100,
(52, 50): 1326,
(53, 3): 23426,
(53, 4): 292825,
(53, 5): 2869685,
(53, 6): 22957480,
(53, 7): 154143080,
(53, 8): 886322710,
(53, 9): 4431613550,
(53, 10): 19499099620,
(53, 11): 76223753060,
(53, 12): 266783135710,
(53, 13): 841392966470,
(53, 14): 2403979904200,
(53, 15): 6250347750920,
(53, 16): 14844575908435,
(53, 17): 32308782859535,
(53, 18): 64617565719070,
(53, 19): 119032357903550,
(53, 20): 202355008436035,
(53, 21): 317986441828055,
(53, 22): 462525733568080,
(53, 23): 623404249591760,
(53, 24): 779255311989700,
(53, 25): 903936161908052,
(53, 26): 973469712824056,
(53, 27): 973469712824056,
(53, 28): 903936161908052,
(53, 29): 779255311989700,
(53, 30): 623404249591760,
(53, 31): 462525733568080,
(53, 32): 317986441828055,
(53, 33): 202355008436035,
(53, 34): 119032357903550,
(53, 35): 64617565719070,
(53, 36): 32308782859535,
(53, 37): 14844575908435,
(53, 38): 6250347750920,
(53, 39): 2403979904200,
(53, 40): 841392966470,
(53, 41): 266783135710,
(53, 42): 76223753060,
(53, 43): 19499099620,
(53, 44): 4431613550,
(53, 45): 886322710,
(53, 46): 154143080,
(53, 47): 22957480,
(53, 48): 2869685,
(53, 49): 292825,
(53, 50): 23426,
(54, 4): 316251,
(54, 5): 3162510,
(54, 6): 25827165,
(54, 7): 177100560,
(54, 8): 1040465790,
(54, 9): 5317936260,
(54, 10): 23930713170,
(54, 11): 95722852680,
(54, 12): 343006888770,
(54, 13): 1108176102180,
(54, 14): 3245372870670,
(54, 15): 8654327655120,
(54, 16): 21094923659355,
(54, 17): 47153358767970,
(54, 18): 96926348578605,
(54, 19): 183649923622620,
(54, 20): 321387366339585,
(54, 21): 520341450264090,
(54, 22): 780512175396135,
(54, 23): 1085929983159840,
(54, 24): 1402659561581460,
(54, 25): 1683191473897752,
(54, 26): 1877405874732108,
(54, 27): 1946939425648112,
(54, 28): 1877405874732108,
(54, 29): 1683191473897752,
(54, 30): 1402659561581460,
(54, 31): 1085929983159840,
(54, 32): 780512175396135,
(54, 33): 520341450264090,
(54, 34): 321387366339585,
(54, 35): 183649923622620,
(54, 36): 96926348578605,
(54, 37): 47153358767970,
(54, 38): 21094923659355,
(54, 39): 8654327655120,
(54, 40): 3245372870670,
(54, 41): 1108176102180,
(54, 42): 343006888770,
(54, 43): 95722852680,
(54, 44): 23930713170,
(54, 45): 5317936260,
(54, 46): 1040465790,
(54, 47): 177100560,
(54, 48): 25827165,
(54, 49): 3162510,
(54, 50): 316251,
(55, 5): 3478761,
(55, 6): 28989675,
(55, 7): 202927725,
(55, 8): 1217566350,
(55, 9): 6358402050,
(55, 10): 29248649430,
(55, 11): 119653565850,
(55, 12): 438729741450,
(55, 13): 1451182990950,
(55, 14): 4353548972850,
(55, 15): 11899700525790,
(55, 16): 29749251314475,
(55, 17): 68248282427325,
(55, 18): 144079707346575,
(55, 19): 280576272201225,
(55, 20): 505037289962205,
(55, 21): 841728816603675,
(55, 22): 1300853625660225,
(55, 23): 1866442158555975,
(55, 24): 2488589544741300,
(55, 25): 3085851035479212,
(55, 26): 3560597348629860,
(55, 27): 3824345300380220,
(55, 28): 3824345300380220,
(55, 29): 3560597348629860,
(55, 30): 3085851035479212,
(55, 31): 2488589544741300,
(55, 32): 1866442158555975,
(55, 33): 1300853625660225,
(55, 34): 841728816603675,
(55, 35): 505037289962205,
(55, 36): 280576272201225,
(55, 37): 144079707346575,
(55, 38): 68248282427325,
(55, 39): 29749251314475,
(55, 40): 11899700525790,
(55, 41): 4353548972850,
(55, 42): 1451182990950,
(55, 43): 438729741450,
(55, 44): 119653565850,
(55, 45): 29248649430,
(55, 46): 6358402050,
(55, 47): 1217566350,
(55, 48): 202927725,
(55, 49): 28989675,
(55, 50): 3478761,
(56, 6): 32468436,
(56, 7): 231917400,
(56, 8): 1420494075,
(56, 9): 7575968400,
(56, 10): 35607051480,
(56, 11): 148902215280,
(56, 12): 558383307300,
(56, 13): 1889912732400,
(56, 14): 5804731963800,
(56, 15): 16253249498640,
(56, 16): 41648951840265,
(56, 17): 97997533741800,
(56, 18): 212327989773900,
(56, 19): 424655979547800,
(56, 20): 785613562163430,
(56, 21): 1346766106565880,
(56, 22): 2142582442263900,
(56, 23): 3167295784216200,
(56, 24): 4355031703297275,
(56, 25): 5574440580220512,
(56, 26): 6646448384109072,
(56, 27): 7384942649010080,
(56, 28): 7648690600760440,
(56, 29): 7384942649010080,
(56, 30): 6646448384109072,
(56, 31): 5574440580220512,
(56, 32): 4355031703297275,
(56, 33): 3167295784216200,
(56, 34): 2142582442263900,
(56, 35): 1346766106565880,
(56, 36): 785613562163430,
(56, 37): 424655979547800,
(56, 38): 212327989773900,
(56, 39): 97997533741800,
(56, 40): 41648951840265,
(56, 41): 16253249498640,
(56, 42): 5804731963800,
(56, 43): 1889912732400,
(56, 44): 558383307300,
(56, 45): 148902215280,
(56, 46): 35607051480,
(56, 47): 7575968400,
(56, 48): 1420494075,
(56, 49): 231917400,
(56, 50): 32468436,
(57, 7): 264385836,
(57, 8): 1652411475,
(57, 9): 8996462475,
(57, 10): 43183019880,
(57, 11): 184509266760,
(57, 12): 707285522580,
(57, 13): 2448296039700,
(57, 14): 7694644696200,
(57, 15): 22057981462440,
(57, 16): 57902201338905,
(57, 17): 139646485582065,
(57, 18): 310325523515700,
(57, 19): 636983969321700,
(57, 20): 1210269541711230,
(57, 21): 2132379668729310,
(57, 22): 3489348548829780,
(57, 23): 5309878226480100,
(57, 24): 7522327487513475,
(57, 25): 9929472283517787,
(57, 26): 12220888964329584,
(57, 27): 14031391033119152,
(57, 28): 15033633249770520,
(57, 29): 15033633249770520,
(57, 30): 14031391033119152,
(57, 31): 12220888964329584,
(57, 32): 9929472283517787,
(57, 33): 7522327487513475,
(57, 34): 5309878226480100,
(57, 35): 3489348548829780,
(57, 36): 2132379668729310,
(57, 37): 1210269541711230,
(57, 38): 636983969321700,
(57, 39): 310325523515700,
(57, 40): 139646485582065,
(57, 41): 57902201338905,
(57, 42): 22057981462440,
(57, 43): 7694644696200,
(57, 44): 2448296039700,
(57, 45): 707285522580,
(57, 46): 184509266760,
(57, 47): 43183019880,
(57, 48): 8996462475,
(57, 49): 1652411475,
(57, 50): 264385836,
(58, 8): 1916797311,
(58, 9): 10648873950,
(58, 10): 52179482355,
(58, 11): 227692286640,
(58, 12): 891794789340,
(58, 13): 3155581562280,
(58, 14): 10142940735900,
(58, 15): 29752626158640,
(58, 16): 79960182801345,
(58, 17): 197548686920970,
(58, 18): 449972009097765,
(58, 19): 947309492837400,
(58, 20): 1847253511032930,
(58, 21): 3342649210440540,
(58, 22): 5621728217559090,
(58, 23): 8799226775309880,
(58, 24): 12832205713993575,
(58, 25): 17451799771031262,
(58, 26): 22150361247847371,
(58, 27): 26252279997448736,
(58, 28): 29065024282889672,
(58, 29): 30067266499541040,
(58, 30): 29065024282889672,
(58, 31): 26252279997448736,
(58, 32): 22150361247847371,
(58, 33): 17451799771031262,
(58, 34): 12832205713993575,
(58, 35): 8799226775309880,
(58, 36): 5621728217559090,
(58, 37): 3342649210440540,
(58, 38): 1847253511032930,
(58, 39): 947309492837400,
(58, 40): 449972009097765,
(58, 41): 197548686920970,
(58, 42): 79960182801345,
(58, 43): 29752626158640,
(58, 44): 10142940735900,
(58, 45): 3155581562280,
(58, 46): 891794789340,
(58, 47): 227692286640,
(58, 48): 52179482355,
(58, 49): 10648873950,
(58, 50): 1916797311,
(59, 9): 12565671261,
(59, 10): 62828356305,
(59, 11): 279871768995,
(59, 12): 1119487075980,
(59, 13): 4047376351620,
(59, 14): 13298522298180,
(59, 15): 39895566894540,
(59, 16): 109712808959985,
(59, 17): 277508869722315,
(59, 18): 647520696018735,
(59, 19): 1397281501935165,
(59, 20): 2794563003870330,
(59, 21): 5189902721473470,
(59, 22): 8964377427999630,
(59, 23): 14420954992868970,
(59, 24): 21631432489303455,
(59, 25): 30284005485024837,
(59, 26): 39602161018878633,
(59, 27): 48402641245296107,
(59, 28): 55317304280338408,
(59, 29): 59132290782430712,
(59, 30): 59132290782430712,
(59, 31): 55317304280338408,
(59, 32): 48402641245296107,
(59, 33): 39602161018878633,
(59, 34): 30284005485024837,
(59, 35): 21631432489303455,
(59, 36): 14420954992868970,
(59, 37): 8964377427999630,
(59, 38): 5189902721473470,
(59, 39): 2794563003870330,
(59, 40): 1397281501935165,
(59, 41): 647520696018735,
(59, 42): 277508869722315,
(59, 43): 109712808959985,
(59, 44): 39895566894540,
(59, 45): 13298522298180,
(59, 46): 4047376351620,
(59, 47): 1119487075980,
(59, 48): 279871768995,
(59, 49): 62828356305,
(59, 50): 12565671261,
(60, 10): 75394027566,
(60, 11): 342700125300,
(60, 12): 1399358844975,
(60, 13): 5166863427600,
(60, 14): 17345898649800,
(60, 15): 53194089192720,
(60, 16): 149608375854525,
(60, 17): 387221678682300,
(60, 18): 925029565741050,
(60, 19): 2044802197953900,
(60, 20): 4191844505805495,
(60, 21): 7984465725343800,
(60, 22): 14154280149473100,
(60, 23): 23385332420868600,
(60, 24): 36052387482172425,
(60, 25): 51915437974328292,
(60, 26): 69886166503903470,
(60, 27): 88004802264174740,
(60, 28): 103719945525634515,
(60, 29): 114449595062769120,
(60, 30): 118264581564861424,
(60, 31): 114449595062769120,
(60, 32): 103719945525634515,
(60, 33): 88004802264174740,
(60, 34): 69886166503903470,
(60, 35): 51915437974328292,
(60, 36): 36052387482172425,
(60, 37): 23385332420868600,
(60, 38): 14154280149473100,
(60, 39): 7984465725343800,
(60, 40): 4191844505805495,
(60, 41): 2044802197953900,
(60, 42): 925029565741050,
(60, 43): 387221678682300,
(60, 44): 149608375854525,
(60, 45): 53194089192720,
(60, 46): 17345898649800,
(60, 47): 5166863427600,
(60, 48): 1399358844975,
(60, 49): 342700125300,
(60, 50): 75394027566,
(61, 11): 418094152866,
(61, 12): 1742058970275,
(61, 13): 6566222272575,
(61, 14): 22512762077400,
(61, 15): 70539987842520,
(61, 16): 202802465047245,
(61, 17): 536830054536825,
(61, 18): 1312251244423350,
(61, 19): 2969831763694950,
(61, 20): 6236646703759395,
(61, 21): 12176310231149295,
(61, 22): 22138745874816900,
(61, 23): 37539612570341700,
(61, 24): 59437719903041025,
(61, 25): 87967825456500717,
(61, 26): 121801604478231762,
(61, 27): 157890968768078210,
(61, 28): 191724747789809255,
(61, 29): 218169540588403635,
(61, 30): 232714176627630544,
(61, 31): 232714176627630544,
(61, 32): 218169540588403635,
(61, 33): 191724747789809255,
(61, 34): 157890968768078210,
(61, 35): 121801604478231762,
(61, 36): 87967825456500717,
(61, 37): 59437719903041025,
(61, 38): 37539612570341700,
(61, 39): 22138745874816900,
(61, 40): 12176310231149295,
(61, 41): 6236646703759395,
(61, 42): 2969831763694950,
(61, 43): 1312251244423350,
(61, 44): 536830054536825,
(61, 45): 202802465047245,
(61, 46): 70539987842520,
(61, 47): 22512762077400,
(61, 48): 6566222272575,
(61, 49): 1742058970275,
(61, 50): 418094152866,
(62, 12): 2160153123141,
(62, 13): 8308281242850,
(62, 14): 29078984349975,
(62, 15): 93052749919920,
(62, 16): 273342452889765,
(62, 17): 739632519584070,
(62, 18): 1849081298960175,
(62, 19): 4282083008118300,
(62, 20): 9206478467454345,
(62, 21): 18412956934908690,
(62, 22): 34315056105966195,
(62, 23): 59678358445158600,
(62, 24): 96977332473382725,
(62, 25): 147405545359541742,
(62, 26): 209769429934732479,
(62, 27): 279692573246309972,
(62, 28): 349615716557887465,
(62, 29): 409894288378212890,
(62, 30): 450883717216034179,
(62, 31): 465428353255261088,
(62, 32): 450883717216034179,
(62, 33): 409894288378212890,
(62, 34): 349615716557887465,
(62, 35): 279692573246309972,
(62, 36): 209769429934732479,
(62, 37): 147405545359541742,
(62, 38): 96977332473382725,
(62, 39): 59678358445158600,
(62, 40): 34315056105966195,
(62, 41): 18412956934908690,
(62, 42): 9206478467454345,
(62, 43): 4282083008118300,
(62, 44): 1849081298960175,
(62, 45): 739632519584070,
(62, 46): 273342452889765,
(62, 47): 93052749919920,
(62, 48): 29078984349975,
(62, 49): 8308281242850,
(62, 50): 2160153123141,
(63, 13): 10468434365991,
(63, 14): 37387265592825,
(63, 15): 122131734269895,
(63, 16): 366395202809685,
(63, 17): 1012974972473835,
(63, 18): 2588713818544245,
(63, 19): 6131164307078475,
(63, 20): 13488561475572645,
(63, 21): 27619435402363035,
(63, 22): 52728013040874885,
(63, 23): 93993414551124795,
(63, 24): 156655690918541325,
(63, 25): 244382877832924467,
(63, 26): 357174975294274221,
(63, 27): 489462003181042451,
(63, 28): 629308289804197437,
(63, 29): 759510004936100355,
(63, 30): 860778005594247069,
(63, 31): 916312070471295267,
(63, 32): 916312070471295267,
(63, 33): 860778005594247069,
(63, 34): 759510004936100355,
(63, 35): 629308289804197437,
(63, 36): 489462003181042451,
(63, 37): 357174975294274221,
(63, 38): 244382877832924467,
(63, 39): 156655690918541325,
(63, 40): 93993414551124795,
(63, 41): 52728013040874885,
(63, 42): 27619435402363035,
(63, 43): 13488561475572645,
(63, 44): 6131164307078475,
(63, 45): 2588713818544245,
(63, 46): 1012974972473835,
(63, 47): 366395202809685,
(63, 48): 122131734269895,
(63, 49): 37387265592825,
(63, 50): 10468434365991,
(64, 14): 47855699958816,
(64, 15): 159518999862720,
(64, 16): 488526937079580,
(64, 17): 1379370175283520,
(64, 18): 3601688791018080,
(64, 19): 8719878125622720,
(64, 20): 19619725782651120,
(64, 21): 41107996877935680,
(64, 22): 80347448443237920,
(64, 23): 146721427591999680,
(64, 24): 250649105469666120,
(64, 25): 401038568751465792,
(64, 26): 601557853127198688,
(64, 27): 846636978475316672,
(64, 28): 1118770292985239888,
(64, 29): 1388818294740297792,
(64, 30): 1620288010530347424,
(64, 31): 1777090076065542336,
(64, 32): 1832624140942590534,
(64, 33): 1777090076065542336,
(64, 34): 1620288010530347424,
(64, 35): 1388818294740297792,
(64, 36): 1118770292985239888,
(64, 37): 846636978475316672,
(64, 38): 601557853127198688,
(64, 39): 401038568751465792,
(64, 40): 250649105469666120,
(64, 41): 146721427591999680,
(64, 42): 80347448443237920,
(64, 43): 41107996877935680,
(64, 44): 19619725782651120,
(64, 45): 8719878125622720,
(64, 46): 3601688791018080,
(64, 47): 1379370175283520,
(64, 48): 488526937079580,
(64, 49): 159518999862720,
(64, 50): 47855699958816,
(65, 15): 207374699821536,
(65, 16): 648045936942300,
(65, 17): 1867897112363100,
(65, 18): 4981058966301600,
(65, 19): 12321566916640800,
(65, 20): 28339603908273840,
(65, 21): 60727722660586800,
(65, 22): 121455445321173600,
(65, 23): 227068876035237600,
(65, 24): 397370533061665800,
(65, 25): 651687674221131912,
(65, 26): 1002596421878664480,
(65, 27): 1448194831602515360,
(65, 28): 1965407271460556560,
(65, 29): 2507588587725537680,
(65, 30): 3009106305270645216,
(65, 31): 3397378086595889760,
(65, 32): 3609714217008132870,
(65, 33): 3609714217008132870,
(65, 34): 3397378086595889760,
(65, 35): 3009106305270645216,
(65, 36): 2507588587725537680,
(65, 37): 1965407271460556560,
(65, 38): 1448194831602515360,
(65, 39): 1002596421878664480,
(65, 40): 651687674221131912,
(65, 41): 397370533061665800,
(65, 42): 227068876035237600,
(65, 43): 121455445321173600,
(65, 44): 60727722660586800,
(65, 45): 28339603908273840,
(65, 46): 12321566916640800,
(65, 47): 4981058966301600,
(65, 48): 1867897112363100,
(65, 49): 648045936942300,
(65, 50): 207374699821536,
(66, 16): 855420636763836,
(66, 17): 2515943049305400,
(66, 18): 6848956078664700,
(66, 19): 17302625882942400,
(66, 20): 40661170824914640,
(66, 21): 89067326568860640,
(66, 22): 182183167981760400,
(66, 23): 348524321356411200,
(66, 24): 624439409096903400,
(66, 25): 1049058207282797712,
(66, 26): 1654284096099796392,
(66, 27): 2450791253481179840,
(66, 28): 3413602103063071920,
(66, 29): 4472995859186094240,
(66, 30): 5516694892996182896,
(66, 31): 6406484391866534976,
(66, 32): 7007092303604022630,
(66, 33): 7219428434016265740,
(66, 34): 7007092303604022630,
(66, 35): 6406484391866534976,
(66, 36): 5516694892996182896,
(66, 37): 4472995859186094240,
(66, 38): 3413602103063071920,
(66, 39): 2450791253481179840,
(66, 40): 1654284096099796392,
(66, 41): 1049058207282797712,
(66, 42): 624439409096903400,
(66, 43): 348524321356411200,
(66, 44): 182183167981760400,
(66, 45): 89067326568860640,
(66, 46): 40661170824914640,
(66, 47): 17302625882942400,
(66, 48): 6848956078664700,
(66, 49): 2515943049305400,
(66, 50): 855420636763836,
(67, 17): 3371363686069236,
(67, 18): 9364899127970100,
(67, 19): 24151581961607100,
(67, 20): 57963796707857040,
(67, 21): 129728497393775280,
(67, 22): 271250494550621040,
(67, 23): 530707489338171600,
(67, 24): 972963730453314600,
(67, 25): 1673497616379701112,
(67, 26): 2703342303382594104,
(67, 27): 4105075349580976232,
(67, 28): 5864393356544251760,
(67, 29): 7886597962249166160,
(67, 30): 9989690752182277136,
(67, 31): 11923179284862717872,
(67, 32): 13413576695470557606,
(67, 33): 14226520737620288370,
(67, 34): 14226520737620288370,
(67, 35): 13413576695470557606,
(67, 36): 11923179284862717872,
(67, 37): 9989690752182277136,
(67, 38): 7886597962249166160,
(67, 39): 5864393356544251760,
(67, 40): 4105075349580976232,
(67, 41): 2703342303382594104,
(67, 42): 1673497616379701112,
(67, 43): 972963730453314600,
(67, 44): 530707489338171600,
(67, 45): 271250494550621040,
(67, 46): 129728497393775280,
(67, 47): 57963796707857040,
(67, 48): 24151581961607100,
(67, 49): 9364899127970100,
(67, 50): 3371363686069236,
(68, 18): 12736262814039336,
(68, 19): 33516481089577200,
(68, 20): 82115378669464140,
(68, 21): 187692294101632320,
(68, 22): 400978991944396320,
(68, 23): 801957983888792640,
(68, 24): 1503671219791486200,
(68, 25): 2646461346833015712,
(68, 26): 4376839919762295216,
(68, 27): 6808417652963570336,
(68, 28): 9969468706125227992,
(68, 29): 13750991318793417920,
(68, 30): 17876288714431443296,
(68, 31): 21912870037044995008,
(68, 32): 25336755980333275478,
(68, 33): 27640097433090845976,
(68, 34): 28453041475240576740,
(68, 35): 27640097433090845976,
(68, 36): 25336755980333275478,
(68, 37): 21912870037044995008,
(68, 38): 17876288714431443296,
(68, 39): 13750991318793417920,
(68, 40): 9969468706125227992,
(68, 41): 6808417652963570336,
(68, 42): 4376839919762295216,
(68, 43): 2646461346833015712,
(68, 44): 1503671219791486200,
(68, 45): 801957983888792640,
(68, 46): 400978991944396320,
(68, 47): 187692294101632320,
(68, 48): 82115378669464140,
(68, 49): 33516481089577200,
(68, 50): 12736262814039336,
(69, 19): 46252743903616536,
(69, 20): 115631859759041340,
(69, 21): 269807672771096460,
(69, 22): 588671286046028640,
(69, 23): 1202936975833188960,
(69, 24): 2305629203680278840,
(69, 25): 4150132566624501912,
(69, 26): 7023301266595310928,
(69, 27): 11185257572725865552,
(69, 28): 16777886359088798328,
(69, 29): 23720460024918645912,
(69, 30): 31627280033224861216,
(69, 31): 39789158751476438304,
(69, 32): 47249626017378270486,
(69, 33): 52976853413424121454,
(69, 34): 56093138908331422716,
(69, 35): 56093138908331422716,
(69, 36): 52976853413424121454,
(69, 37): 47249626017378270486,
(69, 38): 39789158751476438304,
(69, 39): 31627280033224861216,
(69, 40): 23720460024918645912,
(69, 41): 16777886359088798328,
(69, 42): 11185257572725865552,
(69, 43): 7023301266595310928,
(69, 44): 4150132566624501912,
(69, 45): 2305629203680278840,
(69, 46): 1202936975833188960,
(69, 47): 588671286046028640,
(69, 48): 269807672771096460,
(69, 49): 115631859759041340,
(69, 50): 46252743903616536,
(70, 20): 161884603662657876,
(70, 21): 385439532530137800,
(70, 22): 858478958817125100,
(70, 23): 1791608261879217600,
(70, 24): 3508566179513467800,
(70, 25): 6455761770304780752,
(70, 26): 11173433833219812840,
(70, 27): 18208558839321176480,
(70, 28): 27963143931814663880,
(70, 29): 40498346384007444240,
(70, 30): 55347740058143507128,
(70, 31): 71416438784701299520,
(70, 32): 87038784768854708790,
(70, 33): 100226479430802391940,
(70, 34): 109069992321755544170,
(70, 35): 112186277816662845432,
(70, 36): 109069992321755544170,
(70, 37): 100226479430802391940,
(70, 38): 87038784768854708790,
(70, 39): 71416438784701299520,
(70, 40): 55347740058143507128,
(70, 41): 40498346384007444240,
(70, 42): 27963143931814663880,
(70, 43): 18208558839321176480,
(70, 44): 11173433833219812840,
(70, 45): 6455761770304780752,
(70, 46): 3508566179513467800,
(70, 47): 1791608261879217600,
(70, 48): 858478958817125100,
(70, 49): 385439532530137800,
(70, 50): 161884603662657876,
(71, 21): 547324136192795676,
(71, 22): 1243918491347262900,
(71, 23): 2650087220696342700,
(71, 24): 5300174441392685400,
(71, 25): 9964327949818248552,
(71, 26): 17629195603524593592,
(71, 27): 29381992672540989320,
(71, 28): 46171702771135840360,
(71, 29): 68461490315822108120,
(71, 30): 95846086442150951368,
(71, 31): 126764178842844806648,
(71, 32): 158455223553556008310,
(71, 33): 187265264199657100730,
(71, 34): 209296471752557936110,
(71, 35): 221256270138418389602,
(71, 36): 221256270138418389602,
(71, 37): 209296471752557936110,
(71, 38): 187265264199657100730,
(71, 39): 158455223553556008310,
(71, 40): 126764178842844806648,
(71, 41): 95846086442150951368,
(71, 42): 68461490315822108120,
(71, 43): 46171702771135840360,
(71, 44): 29381992672540989320,
(71, 45): 17629195603524593592,
(71, 46): 9964327949818248552,
(71, 47): 5300174441392685400,
(71, 48): 2650087220696342700,
(71, 49): 1243918491347262900,
(71, 50): 547324136192795676,
(72, 22): 1791242627540058576,
(72, 23): 3894005712043605600,
(72, 24): 7950261662089028100,
(72, 25): 15264502391210933952,
(72, 26): 27593523553342842144,
(72, 27): 47011188276065582912,
(72, 28): 75553695443676829680,
(72, 29): 114633193086957948480,
(72, 30): 164307576757973059488,
(72, 31): 222610265284995758016,
(72, 32): 285219402396400814958,
(72, 33): 345720487753213109040,
(72, 34): 396561735952215036840,
(72, 35): 430552741890976325712,
(72, 36): 442512540276836779204,
(72, 37): 430552741890976325712,
(72, 38): 396561735952215036840,
(72, 39): 345720487753213109040,
(72, 40): 285219402396400814958,
(72, 41): 222610265284995758016,
(72, 42): 164307576757973059488,
(72, 43): 114633193086957948480,
(72, 44): 75553695443676829680,
(72, 45): 47011188276065582912,
(72, 46): 27593523553342842144,
(72, 47): 15264502391210933952,
(72, 48): 7950261662089028100,
(72, 49): 3894005712043605600,
(72, 50): 1791242627540058576,
(73, 23): 5685248339583664176,
(73, 24): 11844267374132633700,
(73, 25): 23214764053299962052,
(73, 26): 42858025944553776096,
(73, 27): 74604711829408425056,
(73, 28): 122564883719742412592,
(73, 29): 190186888530634778160,
(73, 30): 278940769844931007968,
(73, 31): 386917842042968817504,
(73, 32): 507829667681396572974,
(73, 33): 630939890149613923998,
(73, 34): 742282223705428145880,
(73, 35): 827114477843191362552,
(73, 36): 873065282167813104916,
(73, 37): 873065282167813104916,
(73, 38): 827114477843191362552,
(73, 39): 742282223705428145880,
(73, 40): 630939890149613923998,
(73, 41): 507829667681396572974,
(73, 42): 386917842042968817504,
(73, 43): 278940769844931007968,
(73, 44): 190186888530634778160,
(73, 45): 122564883719742412592,
(73, 46): 74604711829408425056,
(73, 47): 42858025944553776096,
(73, 48): 23214764053299962052,
(73, 49): 11844267374132633700,
(73, 50): 5685248339583664176,
(74, 24): 17529515713716297876,
(74, 25): 35059031427432595752,
(74, 26): 66072789997853738148,
(74, 27): 117462737773962201152,
(74, 28): 197169595549150837648,
(74, 29): 312751772250377190752,
(74, 30): 469127658375565786128,
(74, 31): 665858611887899825472,
(74, 32): 894747509724365390478,
(74, 33): 1138769557831010496972,
(74, 34): 1373222113855042069878,
(74, 35): 1569396701548619508432,
(74, 36): 1700179760011004467468,
(74, 37): 1746130564335626209832,
(74, 38): 1700179760011004467468,
(74, 39): 1569396701548619508432,
(74, 40): 1373222113855042069878,
(74, 41): 1138769557831010496972,
(74, 42): 894747509724365390478,
(74, 43): 665858611887899825472,
(74, 44): 469127658375565786128,
(74, 45): 312751772250377190752,
(74, 46): 197169595549150837648,
(74, 47): 117462737773962201152,
(74, 48): 66072789997853738148,
(74, 49): 35059031427432595752,
(74, 50): 17529515713716297876,
(75, 25): 52588547141148893628,
(75, 26): 101131821425286333900,
(75, 27): 183535527771815939300,
(75, 28): 314632333323113038800,
(75, 29): 509921367799528028400,
(75, 30): 781879430625942976880,
(75, 31): 1134986270263465611600,
(75, 32): 1560606121612265215950,
(75, 33): 2033517067555375887450,
(75, 34): 2511991671686052566850,
(75, 35): 2942618815403661578310,
(75, 36): 3269576461559623975900,
(75, 37): 3446310324346630677300,
(75, 38): 3446310324346630677300,
(75, 39): 3269576461559623975900,
(75, 40): 2942618815403661578310,
(75, 41): 2511991671686052566850,
(75, 42): 2033517067555375887450,
(75, 43): 1560606121612265215950,
(75, 44): 1134986270263465611600,
(75, 45): 781879430625942976880,
(75, 46): 509921367799528028400,
(75, 47): 314632333323113038800,
(75, 48): 183535527771815939300,
(75, 49): 101131821425286333900,
(75, 50): 52588547141148893628,
(76, 26): 153720368566435227528,
(76, 27): 284667349197102273200,
(76, 28): 498167861094928978100,
(76, 29): 824553701122641067200,
(76, 30): 1291800798425471005280,
(76, 31): 1916865700889408588480,
(76, 32): 2695592391875730827550,
(76, 33): 3594123189167641103400,
(76, 34): 4545508739241428454300,
(76, 35): 5454610487089714145160,
(76, 36): 6212195276963285554210,
(76, 37): 6715886785906254653200,
(76, 38): 6892620648693261354600,
(76, 39): 6715886785906254653200,
(76, 40): 6212195276963285554210,
(76, 41): 5454610487089714145160,
(76, 42): 4545508739241428454300,
(76, 43): 3594123189167641103400,
(76, 44): 2695592391875730827550,
(76, 45): 1916865700889408588480,
(76, 46): 1291800798425471005280,
(76, 47): 824553701122641067200,
(76, 48): 498167861094928978100,
(76, 49): 284667349197102273200,
(76, 50): 153720368566435227528,
(77, 27): 438387717763537500728,
(77, 28): 782835210292031251300,
(77, 29): 1322721562217570045300,
(77, 30): 2116354499548112072480,
(77, 31): 3208666499314879593760,
(77, 32): 4612458092765139416030,
(77, 33): 6289715581043371930950,
(77, 34): 8139631928409069557700,
(77, 35): 10000119226331142599460,
(77, 36): 11666805764052999699370,
(77, 37): 12928082062869540207410,
(77, 38): 13608507434599516007800,
(77, 39): 13608507434599516007800,
(77, 40): 12928082062869540207410,
(77, 41): 11666805764052999699370,
(77, 42): 10000119226331142599460,
(77, 43): 8139631928409069557700,
(77, 44): 6289715581043371930950,
(77, 45): 4612458092765139416030,
(77, 46): 3208666499314879593760,
(77, 47): 2116354499548112072480,
(77, 48): 1322721562217570045300,
(77, 49): 782835210292031251300,
(77, 50): 438387717763537500728,
(78, 28): 1221222928055568752028,
(78, 29): 2105556772509601296600,
(78, 30): 3439076061765682117780,
(78, 31): 5325020998862991666240,
(78, 32): 7821124592080019009790,
(78, 33): 10902173673808511346980,
(78, 34): 14429347509452441488650,
(78, 35): 18139751154740212157160,
(78, 36): 21666924990384142298830,
(78, 37): 24594887826922539906780,
(78, 38): 26536589497469056215210,
(78, 39): 27217014869199032015600,
(78, 40): 26536589497469056215210,
(78, 41): 24594887826922539906780,
(78, 42): 21666924990384142298830,
(78, 43): 18139751154740212157160,
(78, 44): 14429347509452441488650,
(78, 45): 10902173673808511346980,
(78, 46): 7821124592080019009790,
(78, 47): 5325020998862991666240,
(78, 48): 3439076061765682117780,
(78, 49): 2105556772509601296600,
(78, 50): 1221222928055568752028,
(79, 29): 3326779700565170048628,
(79, 30): 5544632834275283414380,
(79, 31): 8764097060628673784020,
(79, 32): 13146145590943010676030,
(79, 33): 18723298265888530356770,
(79, 34): 25331521183260952835630,
(79, 35): 32569098664192653645810,
(79, 36): 39806676145124354455990,
(79, 37): 46261812817306682205610,
(79, 38): 51131477324391596121990,
(79, 39): 53753604366668088230810,
(79, 40): 53753604366668088230810,
(79, 41): 51131477324391596121990,
(79, 42): 46261812817306682205610,
(79, 43): 39806676145124354455990,
(79, 44): 32569098664192653645810,
(79, 45): 25331521183260952835630,
(79, 46): 18723298265888530356770,
(79, 47): 13146145590943010676030,
(79, 48): 8764097060628673784020,
(79, 49): 5544632834275283414380,
(79, 50): 3326779700565170048628,
(80, 30): 8871412534840453463008,
(80, 31): 14308729894903957198400,
(80, 32): 21910242651571684460050,
(80, 33): 31869443856831541032800,
(80, 34): 44054819449149483192400,
(80, 35): 57900619847453606481440,
(80, 36): 72375774809317008101800,
(80, 37): 86068488962431036661600,
(80, 38): 97393290141698278327600,
(80, 39): 104885081691059684352800,
(80, 40): 107507208733336176461620,
(80, 41): 104885081691059684352800,
(80, 42): 97393290141698278327600,
(80, 43): 86068488962431036661600,
(80, 44): 72375774809317008101800,
(80, 45): 57900619847453606481440,
(80, 46): 44054819449149483192400,
(80, 47): 31869443856831541032800,
(80, 48): 21910242651571684460050,
(80, 49): 14308729894903957198400,
(80, 50): 8871412534840453463008,
(81, 31): 23180142429744410661408,
(81, 32): 36218972546475641658450,
(81, 33): 53779686508403225492850,
(81, 34): 75924263305981024225200,
(81, 35): 101955439296603089673840,
(81, 36): 130276394656770614583240,
(81, 37): 158444263771748044763400,
(81, 38): 183461779104129314989200,
(81, 39): 202278371832757962680400,
(81, 40): 212392290424395860814420,
(81, 41): 212392290424395860814420,
(81, 42): 202278371832757962680400,
(81, 43): 183461779104129314989200,
(81, 44): 158444263771748044763400,
(81, 45): 130276394656770614583240,
(81, 46): 101955439296603089673840,
(81, 47): 75924263305981024225200,
(81, 48): 53779686508403225492850,
(81, 49): 36218972546475641658450,
(81, 50): 23180142429744410661408,
(82, 32): 59399114976220052319858,
(82, 33): 89998659054878867151300,
(82, 34): 129703949814384249718050,
(82, 35): 177879702602584113899040,
(82, 36): 232231833953373704257080,
(82, 37): 288720658428518659346640,
(82, 38): 341906042875877359752600,
(82, 39): 385740150936887277669600,
(82, 40): 414670662257153823494820,
(82, 41): 424784580848791721628840,
(82, 42): 414670662257153823494820,
(82, 43): 385740150936887277669600,
(82, 44): 341906042875877359752600,
(82, 45): 288720658428518659346640,
(82, 46): 232231833953373704257080,
(82, 47): 177879702602584113899040,
(82, 48): 129703949814384249718050,
(82, 49): 89998659054878867151300,
(82, 50): 59399114976220052319858,
(83, 33): 149397774031098919471158,
(83, 34): 219702608869263116869350,
(83, 35): 307583652416968363617090,
(83, 36): 410111536555957818156120,
(83, 37): 520952492381892363603720,
(83, 38): 630626701304396019099240,
(83, 39): 727646193812764637422200,
(83, 40): 800410813194041101164420,
(83, 41): 839455243105945545123660,
(83, 42): 839455243105945545123660,
(83, 43): 800410813194041101164420,
(83, 44): 727646193812764637422200,
(83, 45): 630626701304396019099240,
(83, 46): 520952492381892363603720,
(83, 47): 410111536555957818156120,
(83, 48): 307583652416968363617090,
(83, 49): 219702608869263116869350,
(83, 50): 149397774031098919471158,
(84, 34): 369100382900362036340508,
(84, 35): 527286261286231480486440,
(84, 36): 717695188972926181773210,
(84, 37): 931064028937850181759840,
(84, 38): 1151579193686288382702960,
(84, 39): 1358272895117160656521440,
(84, 40): 1528057007006805738586620,
(84, 41): 1639866056299986646288080,
(84, 42): 1678910486211891090247320,
(84, 43): 1639866056299986646288080,
(84, 44): 1528057007006805738586620,
(84, 45): 1358272895117160656521440,
(84, 46): 1151579193686288382702960,
(84, 47): 931064028937850181759840,
(84, 48): 717695188972926181773210,
(84, 49): 527286261286231480486440,
(84, 50): 369100382900362036340508,
(85, 35): 896386644186593516826948,
(85, 36): 1244981450259157662259650,
(85, 37): 1648759217910776363533050,
(85, 38): 2082643222624138564462800,
(85, 39): 2509852088803449039224400,
(85, 40): 2886329902123966395108060,
(85, 41): 3167923063306792384874700,
(85, 42): 3318776542511877736535400,
(85, 43): 3318776542511877736535400,
(85, 44): 3167923063306792384874700,
(85, 45): 2886329902123966395108060,
(85, 46): 2509852088803449039224400,
(85, 47): 2082643222624138564462800,
(85, 48): 1648759217910776363533050,
(85, 49): 1244981450259157662259650,
(85, 50): 896386644186593516826948,
(86, 36): 2141368094445751179086598,
(86, 37): 2893740668169934025792700,
(86, 38): 3731402440534914927995850,
(86, 39): 4592495311427587603687200,
(86, 40): 5396181990927415434332460,
(86, 41): 6054252965430758779982760,
(86, 42): 6486699605818670121410100,
(86, 43): 6637553085023755473070800,
(86, 44): 6486699605818670121410100,
(86, 45): 6054252965430758779982760,
(86, 46): 5396181990927415434332460,
(86, 47): 4592495311427587603687200,
(86, 48): 3731402440534914927995850,
(86, 49): 2893740668169934025792700,
(86, 50): 2141368094445751179086598,
(87, 37): 5035108762615685204879298,
(87, 38): 6625143108704848953788550,
(87, 39): 8323897751962502531683050,
(87, 40): 9988677302355003038019660,
(87, 41): 11450434956358174214315220,
(87, 42): 12540952571249428901392860,
(87, 43): 13124252690842425594480900,
(87, 44): 13124252690842425594480900,
(87, 45): 12540952571249428901392860,
(87, 46): 11450434956358174214315220,
(87, 47): 9988677302355003038019660,
(87, 48): 8323897751962502531683050,
(87, 49): 6625143108704848953788550,
(87, 50): 5035108762615685204879298,
(88, 38): 11660251871320534158667848,
(88, 39): 14949040860667351485471600,
(88, 40): 18312575054317505569702710,
(88, 41): 21439112258713177252334880,
(88, 42): 23991387527607603115708080,
(88, 43): 25665205262091854495873760,
(88, 44): 26248505381684851188961800,
(88, 45): 25665205262091854495873760,
(88, 46): 23991387527607603115708080,
(88, 47): 21439112258713177252334880,
(88, 48): 18312575054317505569702710,
(88, 49): 14949040860667351485471600,
(88, 50): 11660251871320534158667848,
(89, 39): 26609292731987885644139448,
(89, 40): 33261615914984857055174310,
(89, 41): 39751687313030682822037590,
(89, 42): 45430499786320780368042960,
(89, 43): 49656592789699457611581840,
(89, 44): 51913710643776705684835560,
(89, 45): 51913710643776705684835560,
(89, 46): 49656592789699457611581840,
(89, 47): 45430499786320780368042960,
(89, 48): 39751687313030682822037590,
(89, 49): 33261615914984857055174310,
(89, 50): 26609292731987885644139448,
(90, 40): 59870908646972742699313758,
(90, 41): 73013303228015539877211900,
(90, 42): 85182187099351463190080550,
(90, 43): 95087092576020237979624800,
(90, 44): 101570303433476163296417400,
(90, 45): 103827421287553411369671120,
(90, 46): 101570303433476163296417400,
(90, 47): 95087092576020237979624800,
(90, 48): 85182187099351463190080550,
(90, 49): 73013303228015539877211900,
(90, 50): 59870908646972742699313758,
(91, 41): 132884211874988282576525658,
(91, 42): 158195490327367003067292450,
(91, 43): 180269279675371701169705350,
(91, 44): 196657396009496401276042200,
(91, 45): 205397724721029574666088520,
(91, 46): 205397724721029574666088520,
(91, 47): 196657396009496401276042200,
(91, 48): 180269279675371701169705350,
(91, 49): 158195490327367003067292450,
(91, 50): 132884211874988282576525658,
(92, 42): 291079702202355285643818108,
(92, 43): 338464770002738704236997800,
(92, 44): 376926675684868102445747550,
(92, 45): 402055120730525975942130720,
(92, 46): 410795449442059149332177040,
(92, 47): 402055120730525975942130720,
(92, 48): 376926675684868102445747550,
(92, 49): 338464770002738704236997800,
(92, 50): 291079702202355285643818108,
(93, 43): 629544472205093989880815908,
(93, 44): 715391445687606806682745350,
(93, 45): 778981796415394078387878270,
(93, 46): 812850570172585125274307760,
(93, 47): 812850570172585125274307760,
(93, 48): 778981796415394078387878270,
(93, 49): 715391445687606806682745350,
(93, 50): 629544472205093989880815908,
(94, 44): 1344935917892700796563561258,
(94, 45): 1494373242103000885070623620,
(94, 46): 1591832366587979203662186030,
(94, 47): 1625701140345170250548615520,
(94, 48): 1591832366587979203662186030,
(94, 49): 1494373242103000885070623620,
(94, 50): 1344935917892700796563561258,
(95, 45): 2839309159995701681634184878,
(95, 46): 3086205608690980088732809650,
(95, 47): 3217533506933149454210801550,
(95, 48): 3217533506933149454210801550,
(95, 49): 3086205608690980088732809650,
(95, 50): 2839309159995701681634184878,
(96, 46): 5925514768686681770366994528,
(96, 47): 6303739115624129542943611200,
(96, 48): 6435067013866298908421603100,
(96, 49): 6303739115624129542943611200,
(96, 50): 5925514768686681770366994528,
(97, 47): 12229253884310811313310605728,
(97, 48): 12738806129490428451365214300,
(97, 49): 12738806129490428451365214300,
(97, 50): 12229253884310811313310605728,
(98, 48): 24968060013801239764675820028,
(98, 49): 25477612258980856902730428600,
(98, 50): 24968060013801239764675820028,
(99, 49): 50445672272782096667406248628,
(99, 50): 50445672272782096667406248628,
(100, 50): 100891344545564193334812497256}
Programmation dynamique
In [1]:
def binomrow(n):
row = [1]
for r in range(n):
row = [1] + [row[i-1]+row[i] for i in range(1, r+1)] + [1]
return row
In [2]:
[binomrow(i) for i in range(10)]
Out[2]:
[[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
[1, 5, 10, 10, 5, 1],
[1, 6, 15, 20, 15, 6, 1],
[1, 7, 21, 35, 35, 21, 7, 1],
[1, 8, 28, 56, 70, 56, 28, 8, 1],
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]
In [3]:
binomrow(100)[50]
Out[3]:
100891344545564193334812497256
In [ ]:
In [ ]:
In [3]:
def listPerm(l): # Hypothese l est trie
if not l: # l != []
return [[]]
res = []
for i in range(len(l)):
x = l[i]
ll = list(l)
del ll[i]
res.extend([x]+sol for sol in listPerm(ll))
return res
In [4]:
listPerm([])
Out[4]:
[[]]
In [5]:
listPerm([1])
Out[5]:
[[1]]
In [6]:
listPerm([1,2,3])
Out[6]:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
In [7]:
def iterPerm(l):
if not l:
yield []
else:
for i in range(len(l)):
x = l[i]
ll = list(l)
del ll[i]
for sol in listPerm(ll):
yield [x]+sol
In [8]:
list(iterPerm([1,2,3]))
Out[8]:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
In [9]:
listPerm(range(7)) == list(iterPerm(range(7)))
Out[9]:
True
In [ ]:
In [ ]:
In [ ]:
In [10]:
def unrank_perm(l, r):
if not l:
if r == 0:
return []
else:
raise IndexError
reccard = factorial(len(l)-1)
ifirst = r // reccard
irec = r % reccard
l = l[:]
first = l[ifirst]
del l[ifirst]
return [first] + unrank_perm(l, irec)
In [11]:
unrank_perm([1,2,3,4,5], 12)
Out[11]:
[1, 4, 2, 3, 5]
In [14]:
N = 6
[unrank_perm(range(N), i) for i in range(factorial(N))] == listPerm(range(N))
Out[14]:
True
In [ ]:
In [8]:
def multinom(l):
return factorial(sum(l)) / prod(factorial(i) for i in l)
In [9]:
multinom((3,1,0,2))
Out[9]:
60
In [10]:
def unrank_multi(l, r):
if sum(l) == 0:
if r == 0:
return []
else:
raise IndexError
for i in range(len(l)):
if l[i] > 0:
l[i] -= 1
reccard = multinom(l)
if r < reccard:
return [i] + unrank_multi(l, r)
l[i] += 1
r -= reccard
raise IndexError
In [11]:
unrank_multi([3,1,0,2], 45)
Out[11]:
[3, 0, 0, 3, 1, 0]
In [12]:
MS = [3,1,1]
[unrank_multi(MS[:], i) for i in range(multinom(MS))]
Out[12]:
[[0, 0, 0, 1, 2],
[0, 0, 0, 2, 1],
[0, 0, 1, 0, 2],
[0, 0, 1, 2, 0],
[0, 0, 2, 0, 1],
[0, 0, 2, 1, 0],
[0, 1, 0, 0, 2],
[0, 1, 0, 2, 0],
[0, 1, 2, 0, 0],
[0, 2, 0, 0, 1],
[0, 2, 0, 1, 0],
[0, 2, 1, 0, 0],
[1, 0, 0, 0, 2],
[1, 0, 0, 2, 0],
[1, 0, 2, 0, 0],
[1, 2, 0, 0, 0],
[2, 0, 0, 0, 1],
[2, 0, 0, 1, 0],
[2, 0, 1, 0, 0],
[2, 1, 0, 0, 0]]
In [ ]:
In [ ]:
In [ ]:
Content source: hivert/CombiFIIL
Similar notebooks: